package leetcode.D200.T103;

import util.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-12 11:08:00 星期六
 */

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        boolean flag = true;
        Deque<TreeNode> dq = new LinkedList<>();
        List<List<Integer>> results = new ArrayList<>();
        if (root != null)
            dq.addLast(root);
        while(!dq.isEmpty()) {
            int size = dq.size();
            List<Integer> result = new ArrayList<>();
            for(int i=0; i<size; ++i) {
                if (flag) {
                    TreeNode front = dq.removeFirst();
                    result.add(front.val);
                    if (front.left != null)
                        dq.addLast(front.left);
                    if (front.right != null)
                        dq.addLast(front.right);
                } else {
                    TreeNode last = dq.removeLast();
                    result.add(last.val);
                    if (last.right != null)
                        dq.addFirst(last.right);
                    if (last.left != null)
                        dq.addFirst(last.left);
                }
            }
            flag = !flag;
            results.add(result);
        }
        return results;
    }
}